{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 005. Longest Palindromic Substring 最长回文子串\n",
    "\n",
    "### 难度：Medium\n",
    "\n",
    "## 刷题内容\n",
    "\n",
    "> 原题链接\n",
    "\n",
    " - 中文：https://leetcode-cn.com/problems/longest-palindromic-substring/description/\n",
    " - 英文：https://leetcode.com/problems/longest-palindromic-substring/\n",
    " \n",
    "> 内容描述\n",
    "\n",
    "```\n",
    "给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。\n",
    "\n",
    "示例 1：\n",
    "输入: \"babad\"\n",
    "输出: \"bab\"\n",
    "注意: \"aba\"也是一个有效答案。\n",
    "\n",
    "示例 2：\n",
    "输入: \"cbbd\"\n",
    "输出: \"bb\"\n",
    "```\n",
    "\n",
    "## 解题方案\n",
    "\n",
    "> 思路 1\n",
    "\n",
    "如果一个字符串从左向右写和从右向左写是一样的，这样我们就把它叫做回文字符串。如 aba 或者 abba。\n",
    "\n",
    "首先想到的是一个最笨的方法，就是依次把每一个字符当做回文字符串的中间的那个字符，向两边扩展，找到以该字符为中间字符的回文串的最大长度。但是这需要将回文串长度是奇偶的情况分开来讨论。然后接下来要注意的关键是对边界的把握，确保下标不要越界。当子串已经包含首字符或最后一个字符且此时还是回文串的时候，下标分别会向两边多移一位，需要补回来。\n",
    "\n",
    "以 abba 这样一个字符串为例来看，abba 中，一共有偶数个字，第 1 位=倒数第 1 位，第 2 位=倒数第 2 位......第 N 位=倒数第 N 位\n",
    "\n",
    "以 aba 这样一个字符串为例来看，aba 中，一共有奇数个字符，排除掉正中间的那个字符后，第 1 位=倒数第 1 位......第 N 位=倒数第 N 位\n",
    "\n",
    "所以，假设找到一个长度为 len1 的子串后，我们接下去测试它是否满足，第 1 位=倒数第 1 位，第 2 位=倒数第 2 位......第 N 位=倒数第 N 位，也就是说，去测试从头尾到中点，字符是否逐一对应相等。如果一直进行了 [length/2] 次后，对应字符都相等，即满足第 i 位=倒数第 i 位。那么这个子串必然是palindromic string。并且，很容易知道，无论这个字符串长度为奇数还是偶数，都是 palindromic string，因为奇数位数的字符串相当于满足，第中间位=第中间位。\n",
    "\n",
    "于是，现在问题转化为能不能找到一个子串，满足，第 1 位=倒数第 1 位（下文叫做候选子串）。如果有，就对剩下的字符做进一步的检查。\n",
    "\n",
    "我们看一下下面的代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cbc\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return s\n",
    "        # Left index of the target substring\n",
    "        l = 0\n",
    "        # Right index of the target substring\n",
    "        r = 0\n",
    "        # Length of the longest palindromic substring for now \n",
    "        m = 0\n",
    "        # Length of the current substring\n",
    "        c = 0\n",
    "        # Whether the substring contains the first character or last character\n",
    "        # and is palindromic\n",
    "        b = True\n",
    "        # i 设置的是字符串的一个字符\n",
    "        for i in range(0, n):\n",
    "            # 奇数情况\n",
    "            # j 设置的是字符串的 i 字符的左右两边的 j 个字符是不是属于回文串，n-i 限制的是不能超出字符串末尾，i+1 限制的是不能越过字符串的开头\n",
    "            for j in range(0, min(n - i, i + 1)):\n",
    "                # 如果 以 i 字符为中央字符的情况，向两边扩展，不相等的话，代表不是回文串，停止继续比较\n",
    "                if (s[i - j] != s[i + j]):\n",
    "                    b = False\n",
    "                    break\n",
    "                else:\n",
    "                    # 如果以 i 字符为中心字符向左右扩展 j 个字符是回文串，那么现在回文串的长度设置为 c\n",
    "                    c = 2 * j + 1\n",
    "            # 判断 c 与 m 的大小，m 记录的是我们目前为止最长的回文串的长度，如果 c > m，那我们最长回文子串设置为 c ，否则仍然是原来的 m\n",
    "            if (c > m):\n",
    "                # 设置新的回文子串的左 index，b 是 True 就是等于 1，b 是 False 等于 0\n",
    "                l = i - j + 1 - b\n",
    "                # 设置新的回文子串的右 index\n",
    "                r = i + j + b\n",
    "                # 将新的最长回文子串赋值给 m\n",
    "                m = c\n",
    "            b = True\n",
    "            # 偶数情况\n",
    "            # i+1 限制的是不超越字符串的开头，n-i-1 限制的是不超过字符串末尾\n",
    "            for j in range(0, min(n - i - 1, i + 1)):\n",
    "                # 偶数情况下，对应位置上是够相等，相等则是回文串，不相等就不是回文串\n",
    "                if (s[i - j] != s[i + j + 1]):\n",
    "                    b = False\n",
    "                    break\n",
    "                else:\n",
    "                    c = 2 * j + 2\n",
    "            if (c > m):\n",
    "                l = i - j + 1 - b\n",
    "                r = i + j + 1 + b\n",
    "                m = c\n",
    "            b = True\n",
    "        # 将最终的回文串返回\n",
    "        return s[l:r]\n",
    "    \n",
    "s = Solution()\n",
    "nums = \"acbcd\"\n",
    "print(s.longestPalindrome(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面是我们的一个参考版本，算是思路很清晰的。下面这个是 Lisanaaa 大佬根据上面版本进行修改的完成版本，总体思路是相同的，大家可以参考下。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cbc\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        m,l,r = 0,0,0\n",
    "\n",
    "        for i in range(n):\n",
    "            # odd case\n",
    "            for j in range(min(i+1,n-i)):\n",
    "                if s[i-j] != s[i+j]:\n",
    "                    break\n",
    "                if 2*j + 1 > m :\n",
    "                    m = 2 * j + 1\n",
    "                    l = i-j\n",
    "                    r = i+j\n",
    "\n",
    "\n",
    "            if i+1 < n and s[i] == s[i+1]:\n",
    "                for j in range(min(i+1,n-i-1)):\n",
    "                    if s[i-j] != s[i+j+1]:\n",
    "                        break\n",
    "                    if 2 * j + 2 > m :\n",
    "                        m = 2*j +2\n",
    "                        l = i-j\n",
    "                        r = i+j+1\n",
    "\n",
    "\n",
    "        return s[l:r+1]\n",
    "    \n",
    "s = Solution()\n",
    "nums = \"acbcd\"\n",
    "print(s.longestPalindrome(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 思路 2\n",
    "\n",
    "很明显的一个动态规划思路。\n",
    "\n",
    " - 这个问题可以联想我们之前做的动态规划的问题，也就是 72 题，思想是一样的，但是相对于我们的 72 题来说，已经是相当简单了。\n",
    " - 一个比较好的想法是 s 和 reverse(s) 共有的最长的 substring 就是 longest palindromic substring，这样我们就把问题转化为求 Longest common substring 问题了。\n",
    " - 我们来看一下下面的代码，你就懂得了。\n",
    " - 如果还是看不懂，那就去看看我们 72 题的讲解，已经很清楚了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cbc\n"
     ]
    }
   ],
   "source": [
    "class Solution2(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def lcs(s1, s2):\n",
    "            m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]\n",
    "            longest, x_longest = 0, 0\n",
    "            for x in range(1, 1 + len(s1)):\n",
    "                for y in range(1, 1 + len(s2)):\n",
    "                    if s1[x - 1] == s2[y - 1]:\n",
    "                        m[x][y] = m[x - 1][y - 1] + 1\n",
    "                        if m[x][y] > longest:\n",
    "                            longest = m[x][y]\n",
    "                            x_longest = x\n",
    "                    else:\n",
    "                        m[x][y] = 0\n",
    "            return s1[x_longest - longest: x_longest]\n",
    "\n",
    "        return lcs(s, s[::-1])\n",
    "    \n",
    "s_2 = Solution2()\n",
    "nums = \"acbcd\"\n",
    "print(s_2.longestPalindrome(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "典型的动态规划问题。\n",
    "\n",
    "伪码如下：\n",
    "\n",
    "LCSuff(S1...p, T1...q) = LCS(S1...p1, T1...q-1) if S[p] = T[q] else 0\n",
    "\n",
    "代码可以参考：\n",
    "\n",
    "https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_2\n",
    "\n",
    "**但是我们上面的动态规划问题，仍然出现了超时的情况。**\n",
    "\n",
    "因为我们以为这样s[::-1]已经很快了.\n",
    "\n",
    "**特别注意：**\n",
    "\n",
    "这个方法是buggy的，看字符串 abcxgcba ,它 reverse 之后是 abcgxcba ,它们有公共字符串，但是这里面没有回文，修复方式是：\n",
    "\n",
    "we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.\n",
    "\n",
    "我觉得的修复方式这样么：\n",
    "\n",
    "```\n",
    "原本     翻转\n",
    "ABXYBA   ABYXBA\n",
    "\n",
    "求出来的substring indices是 0:2 但是这个s1[0:2] 和 s2[0:2]一样，所以不行\n",
    "同理common substring indices还是s[4:6] 和s2[4:6]一样，不行\n",
    "\n",
    "而比如ABAD和 DABA\n",
    "\n",
    "substring indice 一个是0：3， 一个是1:4，这样就没问题\n",
    "```\n",
    "\n",
    "> 思路 3\n",
    "\n",
    "[Manacher算法，我私下叫马拉车算法，哈哈](https://www.felix021.com/blog/read.php?2040)\n",
    "\n",
    "Manacher 算法增加两个辅助变量 id 和 mx ，其中 id 表示最大回文子串中心的位置，mx 则为 id+P[id] ，也就是最大回文子串的边界。得到一个很重要的结论：\n",
    "\n",
    " - 如果 mx > i，那么 P[i] >= Min(P[2 * id - i], mx - i) . 为什么这样说呢，下面解释\n",
    "\n",
    "下面，令 j = 2 * id - i ，也就是说 j 是 i 关于 id 的对称点。\n",
    "\n",
    " - 当 mx - i > P[j] 的时候，以 S[j] 为中心的回文子串包含在以 S[id] 为中心的回文子串中，由于 i 和 j 对称，以 S[i] 为中心的回文子串必然包含在以 S[id] 为中心的回文子串中，所以必有 P[i] = P[j] ； \n",
    "\n",
    " - 当 P[j] >= mx - i 的时候，以 S[j] 为中心的回文子串不一定完全包含于以 S[id] 为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以 S[i] 为中心的回文子串，其向右至少会扩张到 mx 的位置，也就是说 P[i] >= mx - i。至于 mx 之后的部分是否对称，再具体匹配。  所以 P[i] >= Min(P[2 * id - i], mx - i)，因为以 j 为中心的绘回文子串的左边界可能会比 mx 关于 id 的对称点要大，此时只能证明 P[i]=P[2 * id - i]\n",
    "\n",
    " - 此外，对于 mx <= i 的情况，因为无法对 P[i] 做更多的假设，只能让 P[i] = 1，然后再去匹配。\n",
    "\n",
    "在下面的程序中我的 P 数组保存的是，以当前字符为回文子串中心时，该回文子串的长度（不包含当前字符自身）\n",
    "\n",
    "简单地用一个小例子来解释：原字符串为 'qacbcaw' ，一眼就可以看出来最大回文子串是 'acbca' ， 下面是我做的图，累 shi 了！\n",
    "\n",
    "\n",
    "\n",
    "所以最终代码中的 max_i 就是字符 'b' 所对应的 index8 ，start 的值就是 (max_i - P[max_i] - 1) / 2 = 1 ,最终输出结果为 s[1:6] ,即‘acbca’"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cbc\n"
     ]
    }
   ],
   "source": [
    "class Solution3(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def preProcess(s):\n",
    "            if not s:\n",
    "                return ['^', '&']\n",
    "            T = ['^']\n",
    "            for i in s:\n",
    "                T += ['#', i]\n",
    "            T += ['#', '$']\n",
    "            return T\n",
    "        T = preProcess(s)\n",
    "        P = [0] * len(T)\n",
    "        id, mx = 0, 0\n",
    "        for i in range(1, len(T)-1):\n",
    "            j = 2 * id - i\n",
    "            if mx > i:\n",
    "                P[i] = min(P[j], mx-i)\n",
    "            else:\n",
    "                P[i]= 0\n",
    "            while T[i+P[i]+1] == T[i-P[i]-1]:\n",
    "                P[i] += 1\n",
    "            if i + P[i] > mx:\n",
    "                id, mx = i, i + P[i]\n",
    "        max_i = P.index(max(P))    #保存的是当前最大回文子串中心位置的index\n",
    "        start = int((max_i - P[max_i] - 1) / 2)\n",
    "        res = s[start: start + P[max_i]]\n",
    "        return res\n",
    "    \n",
    "s_3 = Solution3()\n",
    "nums = \"acbcd\"\n",
    "print(s_3.longestPalindrome(nums))   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "run code的时候结果会跟expected不一样，但是该input确实2个结果都可以，所以放心地submit吧 还可以转到647题去看一看，也可以用这个算法解"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
